package com.sicheng.蓝桥.练习题.区间最值问题;

import java.util.Scanner;


/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/24 15:56
 */
public class 分块 {

    //优雅的暴力法,将区间分成k块,每一块的长度是根号n
    // [l,r]的区间最值就是 包含的子块的区间最值并上多出来的部分
    //比如 长度为25的序列 可以分成5块。求[3,24]的区间最值

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        int k = (int) Math.sqrt(nums.length);
        int[] maxes = new int[k];
        int max = -1;
        for (int i = 0; i < nums.length; i++) {
            if (i % k == 0) {
                max = nums[i % k];
            }

            max = Math.max(max, nums[i]);
            maxes[i / k] = max;
        }

        System.out.println(query(1, 2));
    }

    //O(n^(0.5))
    private static int query(int i, int j) {
        return -1;
    }
}
